Reflection without Remorse: Revealing a hidden sequence to speed up monadic reflection
Identifieur interne : 000284 ( Main/Exploration ); précédent : 000283; suivant : 000285Reflection without Remorse: Revealing a hidden sequence to speed up monadic reflection
Auteurs : Atze Van Der Ploeg [Pays-Bas] ; Oleg Kiselyov [Japon]Source :
English descriptors
- mix :
Abstract
A series of list appends or monadic binds for many monads per-forms algorithmically worse when left-associated. Continuation-passing style (CPS) is well-known to cure this severe dependenceof performance on the association pattern. The advantage of CPSdwindles or disappears if we have to examine or modify the inter-mediate result of a series of appends or binds, before continuingthe series. Such examination is frequently needed, for example, tocontrol search in non-determinism monads.We present an alternative approach that is just as general as CPSbut more robust: it makes series of binds and other such opera-tions efficient regardless of the association pattern – and also pro-vides efficient access to intermediate results. The key is to representsuch a conceptual sequence as an efficient sequence data structure.Efficient sequence data structures from the literature are homoge-neous and cannot be applied as they are in a type-safe way to seriesof monadic binds. We generalize them totype aligned sequencesand show how to construct their (assuredly order-preserving) im-plementations. We demonstrate that our solution solves previouslyundocumented, severe performance problems in iteratees, LogicTtransformers, free monads and extensible effects
Url:
Affiliations:
Links toward previous steps (curation, corpus...)
- to stream Hal, to step Corpus: 000222
- to stream Hal, to step Curation: 000222
- to stream Hal, to step Checkpoint: 000073
- to stream Main, to step Merge: 000284
- to stream Main, to step Curation: 000284
Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en">Reflection without Remorse: Revealing a hidden sequence to speed up monadic reflection</title><author><name sortKey="Van Der Ploeg, Atze" sort="Van Der Ploeg, Atze" uniqKey="Van Der Ploeg A" first="Atze" last="Van Der Ploeg">Atze Van Der Ploeg</name><affiliation wicri:level="1"><hal:affiliation type="institution" xml:id="struct-300172" status="VALID"><orgName>CWI</orgName><desc><address><country key="NL"></country></address></desc></hal:affiliation><country>Pays-Bas</country></affiliation></author><author><name sortKey="Kiselyov, Oleg" sort="Kiselyov, Oleg" uniqKey="Kiselyov O" first="Oleg" last="Kiselyov">Oleg Kiselyov</name><affiliation wicri:level="1"><hal:affiliation type="institution" xml:id="struct-411278" status="INCOMING"><orgName>University of Tsukuba</orgName><desc><address><country key="JP"></country></address></desc></hal:affiliation><country>Japon</country></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">HAL</idno><idno type="RBID">Hal:hal-01110936</idno><idno type="halId">hal-01110936</idno><idno type="halUri">https://hal.inria.fr/hal-01110936</idno><idno type="url">https://hal.inria.fr/hal-01110936</idno><date when="2014-09-01">2014-09-01</date><idno type="wicri:Area/Hal/Corpus">000222</idno><idno type="wicri:Area/Hal/Curation">000222</idno><idno type="wicri:Area/Hal/Checkpoint">000073</idno><idno type="wicri:Area/Main/Merge">000284</idno><idno type="wicri:Area/Main/Curation">000284</idno><idno type="wicri:Area/Main/Exploration">000284</idno></publicationStmt><sourceDesc><biblStruct><analytic><title xml:lang="en">Reflection without Remorse: Revealing a hidden sequence to speed up monadic reflection</title><author><name sortKey="Van Der Ploeg, Atze" sort="Van Der Ploeg, Atze" uniqKey="Van Der Ploeg A" first="Atze" last="Van Der Ploeg">Atze Van Der Ploeg</name><affiliation wicri:level="1"><hal:affiliation type="institution" xml:id="struct-300172" status="VALID"><orgName>CWI</orgName><desc><address><country key="NL"></country></address></desc></hal:affiliation><country>Pays-Bas</country></affiliation></author><author><name sortKey="Kiselyov, Oleg" sort="Kiselyov, Oleg" uniqKey="Kiselyov O" first="Oleg" last="Kiselyov">Oleg Kiselyov</name><affiliation wicri:level="1"><hal:affiliation type="institution" xml:id="struct-411278" status="INCOMING"><orgName>University of Tsukuba</orgName><desc><address><country key="JP"></country></address></desc></hal:affiliation><country>Japon</country></affiliation></author></analytic></biblStruct></sourceDesc></fileDesc><profileDesc><textClass><keywords scheme="mix" xml:lang="en"><term>data structures</term><term>monads</term><term>performance</term><term>reflection</term></keywords></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">A series of list appends or monadic binds for many monads per-forms algorithmically worse when left-associated. Continuation-passing style (CPS) is well-known to cure this severe dependenceof performance on the association pattern. The advantage of CPSdwindles or disappears if we have to examine or modify the inter-mediate result of a series of appends or binds, before continuingthe series. Such examination is frequently needed, for example, tocontrol search in non-determinism monads.We present an alternative approach that is just as general as CPSbut more robust: it makes series of binds and other such opera-tions efficient regardless of the association pattern – and also pro-vides efficient access to intermediate results. The key is to representsuch a conceptual sequence as an efficient sequence data structure.Efficient sequence data structures from the literature are homoge-neous and cannot be applied as they are in a type-safe way to seriesof monadic binds. We generalize them totype aligned sequencesand show how to construct their (assuredly order-preserving) im-plementations. We demonstrate that our solution solves previouslyundocumented, severe performance problems in iteratees, LogicTtransformers, free monads and extensible effects</div></front></TEI><affiliations><list><country><li>Japon</li><li>Pays-Bas</li></country></list><tree><country name="Pays-Bas"><noRegion><name sortKey="Van Der Ploeg, Atze" sort="Van Der Ploeg, Atze" uniqKey="Van Der Ploeg A" first="Atze" last="Van Der Ploeg">Atze Van Der Ploeg</name></noRegion></country><country name="Japon"><noRegion><name sortKey="Kiselyov, Oleg" sort="Kiselyov, Oleg" uniqKey="Kiselyov O" first="Oleg" last="Kiselyov">Oleg Kiselyov</name></noRegion></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Musique/explor/OperaV1/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000284 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 000284 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Musique
|area= OperaV1
|flux= Main
|étape= Exploration
|type= RBID
|clé= Hal:hal-01110936
|texte= Reflection without Remorse: Revealing a hidden sequence to speed up monadic reflection
}}
| This area was generated with Dilib version V0.6.21. |  |